#include "uf.h"
#include <stdlib.h>
#include <string.h>

int *Init(int num)
{
        int *arr = malloc(sizeof(int) * num);
        if (arr == NULL)
                return NULL;
        for (int i = 0; i < num; i++)
                arr[i] = -1;
        return arr;
}

int Find(int *arr, int x)
{
        while (arr[x] >= 0)
                x = arr[x];
        return x;
}

int Find_op(int *arr, int x)
{
        int root = x;
        while (arr[root] >= 0)
                root = arr[root];
        while (x != root)
        {
                int t = arr[x]; // t指向x的父节点
                arr[x] = root;  // x挂到根结点下
                x = t;
        }
        return root;
}

int Union(int *arr, int root1, int root2)
{
        if (root1 == root2)
                return -1;
        else if (root1 > root2)
                arr[root1] = root2;
        else
                arr[root2] = root1;
        return 0;
}

int Union_op(int *arr, int root1, int root2)
{
        if (root1 == root2)
                return -1;
        else if (arr[root1] > arr[root2]) // root1为小树，root2为大树
        {
                arr[root1] = root2;  //小树合并到大树
                arr[root2] -= root1; //大树的结点数增加
        }
        else
        {
                arr[root2] = root1;  //小树合并到大树
                arr[root1] -= root2; //大树的结点数增加
        }
        return 0;
}